SP27942 PROD1GCD - Product it again

并不会有更好的阅读体验 甚至你在机房还访问不了

$\prod_{i=1}^n\prod_{j=1}^m (i,j)$

$\prod_{d=1}^{\min(n,m)} d^{\sum_{i=1}^n\sum_{j=1}^m [(i,j)=d]}$

$\prod_{d=1}^{\min(n,m)} d^{\sum_{k=1}^{\min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)} \mu(k) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor}$

$\prod_{d=1}^{\min(n,m)} d^{\sum_{dk=1}^{\min(n,m)} \mu(k) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor}$

$\prod_{T=1}^{\min(n,m)} \prod_{d|T}d^{\mu(\frac{T}{d}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor}$

令 $f(n)=\prod_{d|n} (\frac{n}{d})^{\mu(d)}$ , 虽然不是积性函数，仍考虑线性筛。

首先考虑一个式子：

$\prod_{d|n} x^{\mu(d)}=x^{\sum_{d|n} \mu(d)} = x^{[n=1]}$

然后有：

1. $i=1$，$f(i)=1$
2. $i\in prime$ ， $f(i)=i^{\mu(1)} \times 1^{\mu(i)}=i^1\times 1^{-1}=i$
3. $i\not| p$ ， $f[i \times p]=1$
4. $i|p$ ， $f[i \times p]=f[i]$

$3$，$4$ 点可以展开后利用上式化简。

其中 $p$ 为 $i \times p$ 的最小质因子。

ps. 整除分块中 $l-1$ 可能为 $0$ ， 为了方便令 $f(0)=1$。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 1e7 , Mod = 1e9 + 7;

int Quick_pow( int x , int po , int p = Mod ) {
	int Ans = 1;
	for( ; po ; po >>= 1 , x = 1ll * x * x % p )
		if( po & 1 ) Ans = 1ll * Ans * x % p;
	return Ans;
}
int Inv( int x , int p = Mod ) {
	return Quick_pow( x , p - 2 );
}

int prn , prime[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
	f[ 0 ] = 1 , f[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) { prime[ ++ prn ] = i , f[ i ] = i; }
		for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				f[ i * prime[ j ] ] = f[ i ];
				break;
			}
			f[ i * prime[ j ] ] = 1;
		}
	}
	for( int i = 2 ; i <= MAXN ; i ++ ) f[ i ] = 1ll * f[ i - 1 ] * f[ i ] % Mod;
}

int Solve( int n , int m ) {
	int Ans = 1 , k = min( n , m );
	for( int l = 1 , r ; l <= k ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans = 1ll * Ans * Quick_pow( 1ll * f[ r ] * Inv( f[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod;
	}
	return Ans;
}

int t , n , m;
int main( ) {
	sieve( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m);
		printf("%d\n", Solve( n , m ) );
	}
	return 0;
}